CF17E Palisection

答案为所有的回文串组合-不相交的回文串组合。

cntcnt 为回文串个数 , 可以通过计算每个节点的回文串数量求得。

不相交的回文组合也比较好求,先算出以 ii 为左端点和右端点的回文串数量 L[i]L[i] , R[i]R[i]

阅读全文 »

UVA1218 Perfect Service

一道很不错的树形dp。

dp[u][f]dp[u][f] 为以uu为根的子树。

f=0f=0,表示uu为服务器,那么uu的儿子和父亲既可以是服务器,也可以不是。

阅读全文 »

CF767C Garland

首先可以确定的是,如果点权和不为3的倍数,一定不存在合法方案。

记所有点权和为sumsum

容易想到,令 dp[u]dp[u] 表示以 uu 为根的子树的点权和 , 则有转移:

阅读全文 »

SP9934 ALICE - Alice and Bob

这道题的状态挺难设计的。。。

ss 为石子的总数,那么操作次数最多为 s+(n1)s+(n-1)

如果石子数量全不为一,那么先手必胜的条件为 s+(n1)s+(n-1) 为奇数,因为他一定可以保证操作 s+(n1)s+(n-1) 次。

阅读全文 »

UVA1500 Alice and Bob

这道题的状态挺难设计的。。。

ss 为石子的总数,那么操作次数最多为 s+(n1)s+(n-1)

如果石子数量全不为一,那么先手必胜的条件为 s+(n1)s+(n-1) 为奇数,因为他一定可以保证操作 s+(n1)s+(n-1) 次。

阅读全文 »

P2120 [ZJOI2007]仓库建设

did_i 为工厂 ii 到工厂 nn (山底)的距离, dpidp_i 为在第 ii 个工厂建仓库的最小花费。

因为只能向下运,所以第 nn 个工厂必须建仓库存放它自己的产品,答案便为 dpndp_n

边界条件 dp0dp_0 为不建仓库的花费。

阅读全文 »